거스름돈 문제
1. 개요
1. 개요
거스름돈 문제는 주어진 금액을 가능한 한 적은 수의 동전과 지폐로 구성하는 최적화 문제이다. 이 문제는 탐욕 알고리즘의 대표적인 예시로, 각 단계에서 가장 큰 단위의 화폐를 최대한 많이 사용하는 방식으로 해결한다. 자판기, 금융 거래, 계산 시스템 등 현금을 효율적으로 처리해야 하는 다양한 분야에서 실제로 응용된다.
이 문제는 알고리즘과 컴퓨터 과학의 기본적인 학습 주제이며, 조합 최적화 문제의 한 종류로 분류된다. 탐욕 알고리즘은 특정 조건 하에서 항상 최적해를 보장하는데, 이는 사용하는 화폐 체계가 표준 화폐 체계일 때 성립한다. 그러나 모든 화폐 체계에서 탐욕법이 최적해를 찾는 것은 아니며, 이 경우 다이나믹 프로그래밍 등의 다른 접근법이 필요하다.
2. 문제 정의
2. 문제 정의
거스름돈 문제는 특정 금액을 지불하거나 거슬러 줄 때, 주어진 동전과 지폐의 단위를 사용하여 그 금액을 구성하는 방법 중에서 사용한 화폐의 총 개수를 최소화하는 조합 최적화 문제이다. 이 문제는 알고리즘 이론, 특히 탐욕 알고리즘을 설명하는 가장 대표적인 예시로 자주 등장한다.
문제의 핵심은 사용 가능한 화폐의 단위 집합과 목표 금액이 주어졌을 때, 그 금액을 정확히 맞추면서도 필요한 화폐의 개수가 가장 적은 조합을 찾는 것이다. 예를 들어, 한국 원화의 표준 단위인 1원, 10원, 50원, 100원, 500원 동전과 1000원, 5000원, 10000원, 50000원 지폐가 있다고 가정하고, 7,800원을 가장 적은 수의 화폐로 구성하려면 5000원 지폐 1장, 1000원 지폐 2장, 500원 동전 1개, 100원 동전 3개를 사용하면 총 7개로 만들 수 있다.
이 문제는 단순해 보이지만, 사용 가능한 화폐 체계에 따라 최적해를 찾는 방법이 달라진다. 대부분의 현실 통화 체계는 탐욕 알고리즘이 항상 최적해를 찾을 수 있도록 설계되어 있어, 가장 큰 단위의 화폐부터 가능한 많이 사용하는 방법이 효율적이다. 이러한 특성 덕분에 이 문제는 자판기, 금융 거래 시스템, 계산 시스템 등에서 효율적인 현금 처리를 구현하는 데 널리 응용된다.
3. 탐욕 알고리즘 접근법
3. 탐욕 알고리즘 접근법
3.1. 동작 원리
3.1. 동작 원리
거스름돈 문제에서 탐욕 알고리즘의 동작 원리는 매우 직관적이다. 알고리즘은 현재 상태에서 가장 큰 단위의 화폐부터 차례대로 사용하여 거스름돈을 구성한다. 주어진 금액을 만들기 위해 가능한 한 큰 액면가의 동전이나 지폐를 최대한 많이 사용한 후, 남은 금액에 대해 다음으로 큰 액면가의 화폐를 같은 방식으로 적용하는 과정을 반복한다. 이 과정은 남은 금액이 0이 될 때까지 계속된다.
예를 들어, 대한민국의 원 (화폐) 단위(500원, 100원, 50원, 10원)를 사용하여 800원을 거슬러 줄 때, 탐욕 알고리즘은 먼저 500원 동전 한 개를 선택한다. 남은 금액은 300원이 되며, 다음으로 100원 동전 세 개를 선택한다. 이렇게 하면 총 500원 1개와 100원 3개, 즉 네 개의 동전으로 800원을 구성하게 되어 알고리즘이 종료된다.
이러한 접근법은 각 단계에서 지역적으로 최선의 선택을 하기 때문에 탐욕 알고리즘이라 불린다. 이 방법은 특정 화폐 체계 하에서는 항상 최소 개수의 화폐를 사용하는 전역 최적해를 보장한다. 대한민국 원화나 미국 달러처럼 액면가가 서로의 배수 관계를 이루는 경우가 대표적이다. 이러한 조건에서 알고리즘은 간단하고 빠르게 최적해를 찾아낼 수 있어, 자판기나 POS 시스템 같은 실시간 처리가 필요한 계산 시스템에서 널리 활용된다.
3.2. 적용 가능 조건
3.2. 적용 가능 조건
탐욕 알고리즘이 거스름돈 문제에서 항상 최적해를 보장하는 것은 아니다. 이 접근법이 성공적으로 작동하려면 화폐 체계가 특정 조건을 만족해야 한다.
가장 핵심적인 조건은 화폐 단위가 캐나다 달러나 유로와 같은 특정 체계, 즉 "표준" 또는 "정규" 화폐 체계를 따를 때이다. 이러한 체계에서는 각 큰 단위의 동전이 그보다 작은 단위 동전들의 합보다 크지 않을 때 탐욕 알고리즘이 최적해를 찾는다. 예를 들어, 100원, 50원, 10원 체계에서 50원은 10원 동전 5개(50원)와 같지만 그 합보다 크지 않으므로 조건을 만족한다. 반면, 1원, 3원, 4원과 같은 비표준 체계에서는 6원을 거슬러 줄 때 탐욕법은 4원+1원+1원(총 3개)을 선택하지만, 실제 최적해는 3원+3원(총 2개)이므로 최적해를 보장하지 못한다.
따라서 탐욕 알고리즘의 적용 가능 여부는 사용하는 화폐의 단위 구성에 전적으로 의존한다. 실생활의 대부분의 통화 체계는 이 조건을 만족하도록 설계되어 있어, 자판기나 점원이 직관적으로 가장 큰 단위부터 거슬러 주는 방식으로도 최소한의 동전 수를 맞출 수 있다. 그러나 알고리즘 이론이나 특수한 경우를 고려할 때는 화폐 체계를 먼저 확인한 후 적절한 해법(다이나믹 프로그래밍 등)을 선택해야 한다.
4. 다이나믹 프로그래밍 접근법
4. 다이나믹 프로그래밍 접근법
거스름돈 문제를 해결하는 또 다른 방법은 다이나믹 프로그래밍이다. 이 방법은 탐욕 알고리즘이 항상 최적해를 보장하지 못하는 화폐 체계에서 특히 유용하다. 다이나믹 프로그래밍은 큰 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 저장해 중복 계산을 피하는 방식으로 작동한다. 거스름돈 문제에서는 목표 금액을 만들기 위한 최소 동전 개수를 점진적으로 구축해 나간다.
구체적으로, 0원부터 목표 금액까지 각 금액을 만들 수 있는 최소 동전 개수를 저장할 배열을 만든다. 초기값으로 0원은 0개의 동전으로 만들 수 있고, 나머지 금액은 무한대(또는 매우 큰 수)로 설정한다. 이후 각 화폐 단위를 순회하며, 현재 금액에서 해당 화폐 단위를 뺀 금액의 최소 동전 개수에 1을 더한 값과 기존 값을 비교해 더 작은 값으로 갱신한다. 이 과정을 모든 금액과 모든 화폐 단위에 대해 반복하면 최종적으로 목표 금액의 최소 동전 개수를 얻을 수 있다.
이 접근법의 핵심 장점은 모든 가능성을 체계적으로 고려하기 때문에 어떤 화폐 단위 조합이 주어지더라도 항상 최적해를 찾을 수 있다는 점이다. 예를 들어, 화폐 단위가 1, 3, 4원인 체계에서 6원을 만드는 경우, 탐욕법은 4원, 1원, 1원(총 3개)을 선택하지만, 다이나믹 프로그래밍은 3원, 3원(총 2개)이라는 최적해를 정확히 찾아낸다. 따라서 유한 수학이나 조합론적 최적화가 필요한 보다 일반적인 경우에 강력한 도구가 된다.
다만, 이 방법은 시간 복잡도와 공간 복잡도 측면에서 탐욕법보다 비용이 더 든다. 시간 복잡도는 목표 금액과 사용 가능한 동전 종류의 수에 비례하며, 공간 복잡도는 목표 금액에 비례하는 배열을 필요로 한다. 그럼에도 불구하고 정확성을 보장해야 하는 금융 소프트웨어나 자동 거래 시스템 등에서는 다이나믹 프로그래밍 접근법이 선호될 수 있다.
5. 알고리즘 비교
5. 알고리즘 비교
거스름돈 문제를 해결하는 두 가지 주요 알고리즘인 탐욕 알고리즘과 다이나믹 프로그래밍은 각각 장단점이 뚜렷하다. 두 방법의 핵심 차이는 최적해를 보장하는 조건과 계산 비용에 있다.
탐욕 알고리즘은 항상 가장 큰 단위의 화폐부터 사용하는 직관적인 방식을 따른다. 이 방법은 계산 속도가 매우 빠르고 구현이 간단하다는 장점이 있다. 그러나 이 알고리즘이 항상 최소 개수의 화폐를 보장하는 것은 아니다. 탐욕법이 최적해를 보장하려면 해당 화폐 체계가 특별한 성질, 즉 '탐욕적 선택 속성'을 만족해야 한다. 대표적인 예로 미국 달러나 유로의 일반적인 동전 체계(1¢, 5¢, 10¢, 25¢)는 이 조건을 만족한다. 반면, 임의의 화폐 단위가 주어지면, 예를 들어 1, 3, 4원 동전으로 6원을 만들 경우, 탐욕법(4+1+1)은 최적해(3+3)를 찾지 못한다.
반면, 다이나믹 프로그래밍 접근법은 모든 가능한 조합을 체계적으로 검토한다. 이 방법은 주어진 금액에 대해 0원부터 목표 금액까지의 모든 부분 문제를 해결하며, 각 금액을 만드는 데 필요한 최소 동전 개수를 기록한다. 이 과정은 메모이제이션이나 타뷸레이션 기법을 사용한다. 다이나믹 프로그래밍은 어떤 화폐 체계에서도 항상 최적해를 보장한다는 결정적인 장점이 있다. 그러나 그 대가로 탐욕법에 비해 상대적으로 느린 실행 시간과 더 많은 메모리 사용량이 요구된다. 특히 목표 금액이 크고 화폐 종류가 많을수록 이 차이는 두드러진다.
비교 항목 | 탐욕 알고리즘 | 다이나믹 프로그래밍 |
|---|---|---|
최적해 보장 | 특정 화폐 체계에서만 보장 | 모든 경우 보장 |
시간 복잡도 | O(n) (화폐 종류 수 n) | O(n*m) (목표 금액 m) |
공간 복잡도 | O(1) 또는 O(n) | O(m) |
구현 난이도 | 매우 쉬움 | 상대적으로 복잡함 |
주요 사용처 | 표준화된 화폐 체계 (자판기, 점원 계산) | 일반적인 조합 최적화 문제, 변형 문제 |
따라서 실제 금융 시스템이나 자판기처럼 화폐 단위가 표준화되어 탐욕적 속성이 확실한 경우에는 탐욕 알고리즘이 효율성과 간결함 때문에 선호된다. 반면, 화폐 단위가 임의적이거나 문제가 변형된 경우, 또는 최적해 보장이 절대적으로 중요한 경우에는 다이나믹 프로그래밍이 필수적인 해법이 된다.
6. 구현 예시
6. 구현 예시
6.1. 탐욕법 구현
6.1. 탐욕법 구현
거스름돈 문제를 탐욕 알고리즘으로 구현하는 방법은 직관적이고 효율적이다. 기본 아이디어는 가장 큰 단위의 화폐부터 가능한 한 많이 사용하여 목표 금액을 채우는 것이다.
구현 과정은 먼저 사용 가능한 동전 또는 지폐의 단위를 내림차순으로 정렬한다. 그 후, 가장 큰 단위부터 순회하며, 현재 단위로 목표 금액을 나눈 몫을 해당 단위의 사용 개수로 하고, 나머지를 새로운 목표 금액으로 갱신하는 과정을 반복한다. 이 과정은 목표 금액이 0이 될 때까지, 또는 모든 화폐 단위를 확인할 때까지 계속된다.
아래는 파이썬으로 구현한 간단한 예시 코드이다. 이 코드는 주어진 금액과 화폐 단위 리스트를 입력받아, 각 단위별 필요한 개수를 딕셔너리로 반환한다.
```python
def greedy_coin_change(amount, coins):
coins.sort(reverse=True) # 화폐 단위를 내림차순으로 정렬
result = {}
for coin in coins:
if amount >= coin:
count = amount // coin
result[coin] = count
amount -= coin * count
if amount == 0:
break
return result
```
이 구현의 시간 복잡도는 화폐 단위의 수에 비례하는 O(n)이며, 공간 복잡도는 사용된 화폐 단위의 종류 수에 비례한다. 탐욕법이 항상 최적해를 보장하는 것은 아니지만, 대한민국의 원 (화폐)이나 미국의 달러와 같은 특정 화폐 체계 하에서는 최소 동전 수를 찾는 데 효과적으로 적용될 수 있다.
6.2. 다이나믹 프로그래밍 구현
6.2. 다이나믹 프로그래밍 구현
거스름돈 문제를 해결하는 다이나믹 프로그래밍 구현 방식은 탐욕 알고리즘과 달리 모든 화폐 단위 조합을 고려하여 항상 최적해를 보장한다. 이 방법은 주어진 금액 n을 만들기 위한 최소 동전 개수를 저장할 배열 dp를 사용한다. dp[i]는 금액 i를 만드는 데 필요한 최소 동전 개수를 의미하며, 초기값으로 dp[0] = 0을 설정하고 나머지는 무한대(또는 매우 큰 수)로 설정한다.
구현은 주어진 화폐 단위 배열 coins를 순회하며 각 금액 i에 대해 가능한 모든 동전 c를 사용해 dp[i]를 갱신하는 방식으로 진행된다. 핵심 점화식은 dp[i] = min(dp[i], dp[i - c] + 1)이다. 이는 현재 금액 i에서 특정 동전 c를 하나 사용했을 때의 이전 금액 i-c의 최소 동전 개수에 1을 더한 값과 기존 값을 비교해 더 작은 값을 선택하는 과정이다. 이 과정을 금액 1부터 목표 금액 n까지 반복하면 dp[n]에 최소 동전 개수가 저장된다.
알고리즘 요소 | 설명 |
|---|---|
| 인덱스는 금액, 값은 해당 금액을 만드는 최소 동전 수를 저장. |
초기화 |
|
점화식 |
|
시간 복잡도 | O(n * k) (n: 목표 금액, k: 사용 가능한 동전 종류 수). |
공간 복잡도 | O(n). |
이 구현의 장점은 어떤 화폐 체계에서도 최적해를 찾을 수 있다는 것이다. 예를 들어, 동전이 [1, 3, 4] 단위이고 6원을 만드는 경우, 탐욕법은 4+1+1(3개)을 선택하지만, 다이나믹 프로그래밍은 3+3(2개)이라는 실제 최적해를 정확히 찾아낸다. 따라서 화폐 단위가 탐욕법 조건을 만족하지 않는 일반적인 경우나 변형 문제에 널리 적용된다.
7. 응용 및 변형 문제
7. 응용 및 변형 문제
거스름돈 문제는 기본 형태 외에도 다양한 응용 분야와 변형 문제가 존재한다. 가장 직접적인 응용은 자판기나 POS 시스템과 같은 현금 거래가 일어나는 금융 및 소매 시스템에서 효율적인 현금 처리를 구현하는 것이다. 또한 은행의 현금 인출기나 교통카드 충전기의 잔액 환불 시스템에서도 동일한 원리가 적용된다.
이 문제의 주요 변형 중 하나는 각 동전의 개수에 제한이 있는 경우이다. 예를 들어, 특정 액면가의 동전이 무한정 공급되지 않고 유한한 수량만 있을 때, 주어진 금액을 만들 수 있는지 여부를 판단하거나 최소 개수의 동전을 사용하는 방법을 찾는 문제로 확장된다. 이는 자원 제약 하의 조합 최적화 문제로 볼 수 있다.
또 다른 중요한 변형은 동전 체계 자체가 달라지는 경우이다. 탐욕 알고리즘이 항상 최적해를 보장하지 않는 일반적인 화폐 체계에서 최소 동전 개수를 찾는 문제는 다이나믹 프로그래밍의 전형적인 적용 사례가 된다. 이는 특정 국가의 비표준 통화 단위를 모델링하거나, 게임 내 가상 화폐 시스템을 설계할 때 고려해야 할 수 있다.
더 나아가, 거스름돈 문제는 배낭 문제의 특수한 형태로도 해석될 수 있으며, 정수 계획법이나 그래프 이론을 이용한 접근법도 연구된다. 이러한 변형들은 알고리즘 이론 교육에서 기본 개념을 이해하고 더 복잡한 최적화 문제로 나아가는 중요한 교두보 역할을 한다.
